package problem.year2022.February;

/**
 * @author Liu.Liangyuan 15439
 * @version $Id: Day0214.java, v 0.1 2022年02月14日 12:43 下午 Liangmu Exp $$
 */
public class Day0214 {
    public static void main(String[] args) {

    }

    /**
     * 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
     *
     * 请你找出并返回只出现一次的那个数。
     *
     * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param nums 数组参数
     * @return 返回出现一次的数
     */
    public static int singleNonDuplicate(int[] nums) {
        // 有序数组证明从小到大是线性排列的，那么如果元素出现两个，则肯定是成对出现
        // 以2为分界线，可以将元素分解为两个等排列数组，将等排列数组按索引比对即可
        // 如果第一个和第二个不想等，肯定是第一个有问题
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        try {
            for (int i = 0; i < nums.length; i+=2) {
                if (nums[i] != nums[i+1]) {
                    return nums[i];
                }
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            return nums[len-1];
        }
        return nums[len-1];
    }
}
